// first[i]是ai左边所有元素的乘积，end[i]是ai右边所有元素的乘积
// 如果我们要除ai之外其他所有元素的乘积，只要把左边和右边全部乘起来，即first[i]×end[i]
// ai本身既不在first[i]里，也不在end[i]里，因此天然被排除掉了
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] first = new int[n]; // 保存了 nums[i] 左侧所有元素的乘积（前缀积）
        int[] end = new int[n]; // 保存了 nums[i] 右侧所有元素的乘积（后缀积）
        first[0] = 1;
        for(int i = 1; i < n; i++) {
            first[i] = first[i-1] * nums[i-1];
        }

        end[n-1] = 1;
        for(int j = n-2; j >= 0; j--) {
            end[j] = end[j+1] * nums[j+1];
        }

        int[] ret = new int[n]; // 等于“除了 nums[i] 之外所有元素的乘积”
        for(int i = 0; i < n; i++) {
            ret[i] = first[i] * end[i];
        }
        return ret;
    }
}